| 翻訳と辞書 |
| Lindsey–Fox algorithm ： ウィキペディア英語版 |
Lindsey–Fox algorithm
The Lindsey–Fox algorithm, named after Pat Lindsey and Jim Fox, is a numerical algorithm for finding the roots or zeros of a high-degree polynomial with real coefficients over the complex field. It is particularly designed for random coefficients but also works well on polynomials with coefficients from samples of speech, seismic signals, and other measured phenomena. A Matlab implementation of this has factored polynomials of degree over a million on a desk top computer.
== The Lindsey–Fox algorithm==
The Lindsey–Fox algorithm uses the FFT (fast Fourier transform) to very efficiently conduct a grid search in the complex plane to find accurate approximations to the ''N'' roots (zeros) of an ''N''th-degree polynomial. The power of this grid search allows a new polynomial factoring strategy that has proven to be very effective for a certain class of polynomials. This algorithm was conceived of by Pat Lindsey and implemented by Jim Fox in a package of computer programs created to factor high-degree polynomials. It was originally designed and has been further developed to be particularly suited to polynomials with real, random coefficients. In that form, it has proven to be very successful by factoring thousands of polynomials of degrees from one thousand to hundreds of thousand as well as several of degree one million and one each of degree two million and four million. In addition to handling very high degree polynomials, it is accurate, fast, uses minimum memory, and is programmed in the widely available language, Matlab. There are practical applications, often cases where the coefficients are samples of some natural signal such as speech or seismic signals, where the algorithm is appropriate and useful. However, it is certainly possible to create special, ill-conditioned polynomials that it cannot factor, even low degree ones. The basic ideas of the algorithm were first published by Lindsey and Fox in 1992〔J. P. Lindsey and James W. Fox. “A method of factoring long z-transform polynomials”, Computational Methods in Geosciences, SIAM, pp. 78–90, 1992.〕 and reprinted in 1996.〔Osman Osman (editor), Seismic Source Signature Estimation and Measurement, Geophysics Reprint Series #18, Society of Exploration Geophysicists (SEG), 1996, pp. 712–724.〕 After further development, other papers were published in 2003〔Gary A. Sitton, C. Sidney Burrus, James W. Fox, and Sven Treitel. “Factoring very high degree polynomials”. IEEE Signal Processing Magazine, 20(6):27–42, November 2003.〕〔C. S. Burrus, J. W. Fox, G. A. Sitton, and S. Treitel, “Factoring High Degree Polynomials in Signal Processing”, Proceedings of the IEEE DSP Workshop, Taos, NM, Aug. 3, 2004, pp. 156–157.〕 and an on-line booklet. The program was made available to the public in March 2004 on the Rice University web site. A more robust version-2 was released in March 2006 and updated later in the year.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Lindsey–Fox algorithm」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|